package 动态规划;

import java.util.Stack;

//https://leetcode.cn/problems/trapping-rain-water/
public class 接雨水 {
    //动态规划
    public int trap(int[] height) {
        int[] lMax = new int[height.length];
        int[] rMax = new int[height.length];
        lMax[0] = 0;
        rMax[height.length - 1] = 0;
        int result = 0 ;
        for (int i = 1 ; i < height.length ; i ++){
            lMax[i] = Math.max(lMax[i - 1] , height[i - 1]);
        }
        for (int i = height.length - 2 ; i >= 0 ; i --){
            rMax[i] = Math.max(rMax[i + 1] , height[i + 1]);
        }
        for (int i = 0 ; i < height.length - 1 ; i ++){
            int num = Math.min(lMax[i] , rMax[i]);
            result = result + (height[i] < num ? num - height[i] : 0);
        }
        return result;

    }
    //单调栈
    public int trap_2(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int result = 0 , num = 0 ;
        while (num < height.length){
            while (!stack.isEmpty() && height[num] > height[stack.peek()]){
                int i = height[stack.pop()];

                if (stack.isEmpty()){
                    break;
                }
                int min = Math.min(height[num] , height[stack.peek()]);
                int len = num - stack.peek() - 1;
                result = result + (min - i) * len;
            }
            stack.push(num);
            num ++;
        }
        return result;

    }


}
